Celestin Apprentice 2

home *** CD-ROM | disk | FTP | other *** search

/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Generic List Library / generic_list.docs < prev next >

Wrap

Text File | 1994-08-21 | 24.5 KB | 623 lines | [TEXT/R*ch]

************************************************************************* ************************************************************************* ** ** ** Generic List Library ** ** ** ** by Keith Pomakis ** ** kppomaki@jeeves.uwaterloo.ca ** ** ** ** Spring, 1994 ** ** ** ************************************************************************* ************************************************************************* **** Documentation **** **************************************************************************** PURPOSE AND HISTORY **************************************************************************** The basic data structures of lists, stacks and queues are fundamental to programming at almost every level. However, because of the nature of the C programming language, it is difficult to program a set of generic list functions without sacrificing simplicity. Therefore, C programmers often find themselves programming specialized list functions over and over again. This is not only a large waste of effort, but can also be the source of many errors since each individual implementation is often tested only haphazardly. After countless assignments and projects (both academic and personal) in which I found myself constantly rewriting the same list manipulation functions in slightly different contexts, I figured it was about time to take the effort and program an efficient, flexible, and easy-to-use library of generic list functions. And that is exactly what I did! It is my hope that, in distributing this library, others will be able to use what I've put together to increase their own programming productivity. **************************************************************************** DISCLAIMER **************************************************************************** I am releasing this library to the public domain. Therefore, people can use it, copy it, distribute it, modify it, and do whatever they want with it. Although this library has been well thought out, tested, and used in real applications, it is not guaranteed to be bug-free. Therefore, I am not responsible for anything that happens, either directly or indirectly, due to the usage of this library. If you modify or add to this library in any way, I'd appreciate it if you dropped me a line (or Internet packet, whatever) telling me what you did. I'm always interested in potential improvements to my work! Also, if you find any bugs (gasp!) or have any questions or comments about the library, you can contact me as well. My e-mail address is "kppomaki@jeeves.uwaterloo.ca". I'd be interested in hearing what you think! Oh, one other thing... I've put a lot of work into this library, so I'd appreciate it if you kept my name attached to it when distributing or modifying it. **************************************************************************** REQUIREMENTS **************************************************************************** The only requirements for the usage of this library are an ANSI C compiler, a machine to run it on, and a project that is in need of generic list functions! This library has been tested with gcc on a Sun 4 and with Think C on a Macintosh. The code is ANSI-compliant, and should present no problem with any other setup. **************************************************************************** PHILOSOPHY **************************************************************************** My goal when designing this library was to make it as flexible and complete as possible, while still keeping it efficient and easy to use. I have seen and have tried to use other generic list libraries (and yes, I realize they are numerous), but often they have failed me on one or more of the above points. I also realize that such a library would be a trivial piece of work in C++. However, as much of a proponent of the object-oriented paradigm as I am, I tend to dislike C++ because of the hideous syntactic nightmares I get when tackling the language. Therefore, I have decided to write the library in C. A set of basic generic doubly-linked list functions were designed and programmed first (along with a suitable efficient data structure), and then some higher-level functions were added to increase ease of use. The functionality of stacks, queues and sorted lists were then added. In actuality, these functions (with the exception of one of the sorted-list functions) are nothing more than aliases for the appropriate generic list operations. This aliasing is behind the scenes, however, and the user of this library may treat the operation of lists, stacks and queues in this library as completely separate functionality. In order to make the library completely generic, it was designed to manipulate pointers of type void *. Therefore, it is assumed that the programmer is statically or dynamically creating the objects of interest, and using the generic list functions to manipulate them. It is up to the programmer to handle the allocation and deallocation of the memory for the objects themselves. A pointer to the same object may be stored in a list multiple times. The only restriction imposed is that a NULL pointer may not be stored. **************************************************************************** USAGE **************************************************************************** The use of this library is simple and straight-forward. In every source file that requires the use of generic list functions, the line: #include "generic_list.h" must be included at the top of the file. For those who hand-craft their own makefiles, "generic_list.h" should become a prerequisite for each of these files, as well as for "generic_list.c" itself. The library defines three data types: Generic_list Generic_stack Generic_queue The usage of these functions is best illustrated with an example: foo() { Generic_stack stack; My_object *obj; initialize_stack(&stack); obj = new_object(); push(stack, obj); ... obj = pop(stack); free(obj); ... destroy_stack(&stack); } Each list must be initialized before use and should be destroyed after it is no longer needed. The programmer must handle the allocation and deallocation of the memory for the objects being stored. Explicit memory management for the lists is not necessary. **************************************************************************** LIST OF FUNCTIONS **************************************************************************** The following are the headers of the functions provided in the generic list library. They are described in more detail later. Generic Lists ------------- void initialize_list(Generic_list *list); void destroy_list(Generic_list *list); void add_to_beginning(Generic_list list, void *pointer); void add_to_end(Generic_list list, void *pointer); void add_to_list(Generic_list list, void *pointer); void *remove_from_beginning(Generic_list list); void *remove_from_end(Generic_list list); void *remove_from_list(Generic_list list, void *pointer); void *peek_at_beginning(Generic_list list); void *peek_at_end(Generic_list list); void *first_in_list(Generic_list list); void *next_in_list(Generic_list list); void *current_in_list(Generic_list list); void *remove_current(Generic_list list); void *previous_in_list(Generic_list list); void *last_in_list(Generic_list list); void reset_to_beginning(Generic_list list); void reset_to_end(Generic_list list); int num_of_objects(const Generic_list list); int is_empty(const Generic_list list); int is_in_list(const Generic_list list, const void *pointer); Generic_list copy_list(Generic_list list); void perform_on_list (Generic_list list, void (*fn)(void *pointer, void *args), void *args); void *first_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); void *next_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); void *previous_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); void *last_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); Generic_list all_such_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); void remove_all_such_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); Generic Sorted Lists -------------------- void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b)); ...and all Generic_list functions except: void add_to_beginning(Generic_list list, void *pointer); void add_to_end(Generic_list list, void *pointer); void *remove_from_beginning(Generic_list list); void *remove_from_end(Generic_list list); Generic Stacks -------------- void initialize_stack(Generic_stack *stack); void destroy_stack(Generic_stack *stack); void push(Generic_stack stack, void *pointer); void *pop(Generic_stack stack); void pop_all(Generic_stack stack); void *peek_at_top(Generic_stack stack); Generic_stack copy_stack(Generic_stack stack); int is_empty(const Generic_stack stack); Generic Queues -------------- void initialize_queue(Generic_queue *queue); void destroy_queue(Generic_queue *queue); void enqueue(Generic_queue queue, void *pointer); void *dequeue(Generic_queue queue); void dequeue_all(Generic_queue queue); void *peek_at_head(Generic_queue queue); void *peek_at_tail(Generic_queue queue); Generic_queue copy_queue(Generic_queue queue); int is_empty(const Generic_queue queue); **************************************************************************** DETAILED DESCRIPTION OF FUNCTIONS **************************************************************************** Generic Lists ------------- void initialize_list(Generic_list *list); Every list must be initialized before it is used, unless it is the destination of a copy. The only time it is valid to re-initialize a list is after it has been destroyed. void destroy_list(Generic_list *list); When a list is no longer needed, it should be destroyed. This process will automatically remove all remaining objects from the list. However, the memory for these objects will not be reclaimed, so if the objects have no other references, care should be taken to purge the list and free all objects before destroying the list. It is an error to destroy a list more than once (unless it has been re-initialized in the meantime). void add_to_beginning(Generic_list list, void *pointer); This function will add the specified object to the beginning of the list. The pointer must not be NULL. void add_to_end(Generic_list list, void *pointer); This function will add the specified object to the end of the list. The pointer must not be NULL. void add_to_list(Generic_list list, void *pointer); This function will add the specified object to the list. The pointer must not be NULL. void *remove_from_beginning(Generic_list list); This function will remove the first object from the beginning of the list and return it. If the list is empty, NULL is returned. void *remove_from_end(Generic_list list); This function will remove the last object from the end of the list and return it. If the list is empty, NULL is returned. void *remove_from_list(Generic_list list, void *pointer); This function will remove the specified object from the list and return it. If the specified object does not exist in the list, NULL is returned. If the specified object exists in the list more than once, only the last reference to it is removed. void remove_all(Generic_list list); This function will remove all objects from the list. Note that the memory for these objects will not be reclaimed, so if the objects have no other references, they should be removed one at a time, freeing them when necessary. void *peek_at_beginning(Generic_list list); This function will return the first object in the list. If the list is empty, NULL is returned. void *peek_at_end(Generic_list list); This function will return the last object in the list. If the list is empty, NULL is returned. void *first_in_list(Generic_list list); This function will return the first object in the list and mark it as the current object. If the list is empty, NULL is returned. void *next_in_list(Generic_list list); This function will return the next object in the list and mark it as the current object. If the end of the list is reached, or if the list is empty, NULL is returned. void *current_in_list(Generic_list list); This function will return the object in the list that is considered the current object (as defined by the surrounding functions). If the current object has just been removed, if current points to the beginning or end of the list, or if the list is empty, NULL is returned. void *remove_current(Generic_list list); This function will remove the current object from the list and return it. If the current object has already been removed, if current points to the beginning or end of the list, or if the list is empty, NULL is returned. void *previous_in_list(Generic_list list); This function will return the previous object in the list and mark it as the current object. If the beginning of the list is reached, or if the list is empty, NULL is returned. void *last_in_list(Generic_list list); This function will return the last object in the list and mark it as the current object. If the list is empty, NULL is returned. void reset_to_beginning(Generic_list list); This function will reset the list to the beginning. Therefore, current points to the beginning of the list, and the next object in the list is the first object. void reset_to_end(Generic_list list); This function will reset the list to the end. Therefore, current points to the end of the list, and the previous object in the list is the last object. int num_of_objects(const Generic_list list); This function will return the number of objects in the list. int is_empty(const Generic_list list); This function will return TRUE (1) if the list is empty, and FALSE (0) otherwise. int is_in_list(const Generic_list list, const void *pointer); This function will return TRUE (1) if the specified object is a member of the list, and FALSE (0) otherwise. Note that this only compares object pointers. If an identical object is a member of the list, but occupies a different location in memory, this function will return FALSE. Generic_list copy_list(Generic_list list); This function will return a copy of the list. The objects themselves are not copied; only new references to them are made. The new list loses its concept of the current object. The destination of this copy need not be initialized. However, care must be taken to destroy the copy when it is no longer needed. void perform_on_list (Generic_list list, void (*fn)(void *pointer, void *args), void *args); This function will perform the specified function on each object in the list. Any optional arguments required can be passed through args. void *first_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will find and return the first object in the list which causes the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. The found object is then marked as the current object. If no objects in the list meet the criteria of the specified function, NULL is returned. void *next_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will find and return the next object in the list which causes the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. The found object is then marked as the current object. If there are no objects left in the list that meet the criteria of the specified function, NULL is returned. void *previous_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will find and return the previous object in the list which causes the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. The found object is then marked as the current object. If there are no objects left in the list that meet the criteria of the specified function, NULL is returned. void *last_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will find and return the last object in the list which causes the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. The found object is then marked as the current object. If no objects in the list meet the criteria of the specified function, NULL is returned. Generic_list all_such_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will return a new list containing all of the objects in the specified list which cause the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. The objects themselves are not copied; only new references to them are made. Care must be taken to destroy this new list when it is no longer needed. void remove_all_such_that (Generic_list list, int (*fn)(const void *pointer, const void *args), const void *args); This function will remove all objects in the list which cause the specified function to return a TRUE (non-zero) value. Any optional arguments required can be passed through args. Note that the memory for these objects will not be reclaimed, so if the objects have no other references, it is best to avoid this function and remove the objects one by one, freeing them when necessary. Generic Sorted Lists -------------------- void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b)); This function initializes a sorted list. A less-than function must be specified which accepts two pointers, a and b, and returns TRUE (non-zero) if a is less than b, FALSE otherwise. Once a list is initialized in this way, all of the generic list functions described above can be used, except for: void add_to_beginning(Generic_list list, void *pointer); void add_to_end(Generic_list list, void *pointer); void *remove_from_beginning(Generic_list list); void *remove_from_end(Generic_list list); In particular, the function add_to_list() should be used to add objects to the sorted list. This will insure that the list will remain sorted by the criteria specified by the less-than function. The only time it is valid to re-initialize a list is after it has been destroyed. Generic Stacks -------------- void initialize_stack(Generic_stack *stack); Every stack must be initialized before it is used, unless it is the destination of a copy. The only time it is valid to re-initialize a stack is after it has been destroyed. void destroy_stack(Generic_stack *stack); When a stack is no longer needed, it should be destroyed. This process will automatically remove all remaining objects from the stack. However, the memory for these objects will not be reclaimed, so if the objects have no other references, care should be taken to purge the stack and free all objects before destroying the stack. It is an error to destroy a stack more than once (unless it has been re-initialized in the meantime). void push(Generic_stack stack, void *pointer); This function will push the specified object onto the stack. The pointer must not be NULL. void *pop(Generic_stack stack); This function will pop the first object from the top of the stack and return it. If the stack is empty, NULL is returned. void pop_all(Generic_stack stack); This function will pop all objects from the stack. Note that the memory for these objects will not be reclaimed, so if the objects have no other references, they should be popped one at a time, freeing them when necessary. void *peek_at_top(Generic_stack stack); This function will return the object on the top of the stack. If the stack is empty, NULL is returned. Generic_stack copy_stack(Generic_stack stack); This function will return a copy of the stack. The objects themselves are not copied; only new references to them are made. The destination of this copy need not be initialized. However, care must be taken to destroy this copy when it is no longer needed. int is_empty(const Generic_stack stack); This function will return TRUE (1) if the stack is empty, and FALSE (0) otherwise. Generic Queues -------------- void initialize_queue(Generic_queue *queue); Every queue must be initialized before it is used, unless it is the destination of a copy. The only time it is valid to re-initialize a queue is after it has been destroyed. void destroy_queue(Generic_queue *queue); When a queue is no longer needed, it should be destroyed. This process will automatically remove all remaining objects from the queue. However, the memory for these objects will not be reclaimed, so if the objects have no other references, care should be taken to purge the queue and free all objects before destroying the queue. It is an error to destroy a queue more than once (unless it has been re-initialized in the meantime). void enqueue(Generic_queue queue, void *pointer); This function will add the specified object to the tail of the queue. The pointer must not be NULL. void *dequeue(Generic_queue queue); This function will remove the first object from the head of the queue and return it. If the queue is empty, NULL is returned. void dequeue_all(Generic_queue queue); This function will remove all objects from the queue. Note that the memory for these objects will not be reclaimed, so if the objects have no other references, they should be dequeued one at a time, freeing them when necessary. void *peek_at_head(Generic_queue queue); This function will return the object at the head of the queue. If the queue is empty, NULL is returned. void *peek_at_tail(Generic_queue queue); This function will return the object at the tail of the queue. If the queue is empty, NULL is returned. Generic_queue copy_queue(Generic_queue queue); This function will return a copy of the queue. The objects themselves are not copied; only new references to them are made. The destination of this copy need not be initialized. However, care must be taken to destroy this copy when it is no longer needed. int is_empty(const Generic_queue queue); This function will return TRUE (1) if the queue is empty, and FALSE (0) otherwise. **************************************************************************** HINTS AND RECOMMENDATIONS **************************************************************************** Technically, any of the above functions can be used with any of the three data types. For example, one can use perform_on_list() to perform a specified function on every object in a queue, or is_in_list() to determine whether or not a particular object is a member of a stack. One can even pop from a queue and dequeue from a stack. However, such usage is not recommended, as it is contrary to the logical usage of such data structures. A priority queue can be implemented with a sorted list.